package com.wtgroup.demo.mianshi.算法.etc;

import com.wtgroup.demo.common.bean.MultiTreeNode;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.Mock;
import com.wtgroup.demo.common.util.RandomUtil;
import lombok.AllArgsConstructor;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/18 10:24
 */
public class D_递归改迭代_需要返回值 {

    public static void main(String[] args) {
        Judger.of(() -> {
            // MultiTreeNode head = Mock.multiTree(10, 2);
            // MultiTreeNode head = Mock.multiTree(new int[]{720, -126, -279, 592}, 10);
            int[] ints = RandomUtil.randomArray(RandomUtil.randomInt(0, 20), -1000, 1001);
            MultiTreeNode head = Mock.multiTree(ints, RandomUtil.randomInt(1, 10));

            // System.out.println(head);

            int res1 = func_recurse(head);
            // int res2 = func_loop(head);
            int res2 = func_loop_draft(head);

            // 对比 结果1 和 结果2
            boolean ret = res1 == res2;
            if (!ret) {
                // Sout.println(ints);
                System.out.println(res1);
                System.out.println(res2);
            }


            return ret;
        }).setIterCount(100).start().print();
    }

    /**
     * 递归方式求多叉树的最大值
     */
    static int func_recurse(MultiTreeNode head) {
        if (head == null) {
            return Integer.MIN_VALUE;
        }
        List<MultiTreeNode> nexts = head.getNexts();
        nexts = nexts == null ? new ArrayList<>() : nexts;

        if (nexts.size() == 0) {
            // 叶子节点, 不用pk
            return head.getValue();
        }

        // 分支处理
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nexts.size(); i++) {
            MultiTreeNode next = nexts.get(i);
            int max1 = func_recurse(next);
            max = Math.max(max, max1);
        }

        // 后置处理
        return Math.max(max, head.getValue());
    }

    static int func_loop_draft(MultiTreeNode _head) { // 凡是递归里面的动态入参, 都有可能需要封装到 Frame 中
        /*
        1. 入参看情况封装到 Frame 中, 用于压栈,出栈, 记录运行时信息. 一个节点处都会对应一个 Frame
        2. 递归的 base case 原样放到循环内部, 执行完 continue .
        3. 遇到递归调用处, 观察当前 Frame 压过栈的分支偏移量(任务提交过了,处理过了)
            3.1 达到分支个数, 说明, 所有子分支均已处理过, continue 下一轮迭代, 跳到 parent 处, 处理它的下一个子, 即我的后一个分支.
            3.2 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理.
        4. "自身" 处理, 原样放到循环内部对应位置.
         */
        if (_head == null) {
            return Integer.MIN_VALUE;
        }

        Stack<Frame> stack = new Stack<>();
        Frame rootFrame = new Frame(_head, null, null);
        stack.push(rootFrame);

        Map<Frame, Integer> forkOffsetMap = new HashMap<>();

        while (!stack.isEmpty()) {
            Frame currFrame = stack.pop();

            // 叶子结点
            if (currFrame.node.getNexts() == null || currFrame.node.getNexts().isEmpty()) {
                // 结果
                currFrame.result = currFrame.node.getValue();
                continue;
            }

            Integer currSubFork = forkOffsetMap.getOrDefault(currFrame, 0);
            if (currSubFork == currFrame.node.getNexts().size()) {
                // 这里放后置处理逻辑
                // 递归中, 将所有子分支的最大值pk取最大和我自身再pk
                // 所以, 需要用到所有子分支的结果. 怎么知道所有子分支的结果?
                // 思路1: 实时更新. 子节点得到结果后, 立马和父节点当前值pk, 更新它.
                //   当前节点是子节点们已经pk后的结果, 所以这里直接取当前节点的值和父节点pk.
                // 思路2: 子节点每次有结果后, 只需要放到自己的 Frame 里存着就可以了, 这里, 取所有子 Frame 的结果pk, 作为我的结果
                //   ? 怎么获取所有子节点 Frame ?
                // 思路3: 子节点结果上报给父节点, 父节点 Frame 有个容器用于暂存所有子节点的结果, 之后需要用的到时候拿来用, 这里是取最大值, 就是拿来pk

                int max = Integer.MIN_VALUE;
                for (Frame subframe : currFrame.subframes) {
                    max = Math.max(max, subframe.result);
                }
                currFrame.result = max = Math.max(currFrame.node.getValue(), max);
                continue;
            }

            stack.push(currFrame);
            MultiTreeNode currNext = currFrame.node.getNexts().get(currSubFork);
            Frame subframe = new Frame(currNext, null, null);
            stack.push(subframe);
            currFrame.addSubframe(subframe);
            forkOffsetMap.put(currFrame, currSubFork + 1);
        }


        return rootFrame.result;
    }

    @AllArgsConstructor
    static class Frame {
        MultiTreeNode node;
        // 存储当前栈帧的结果, 根据需要, 更换类型
        Integer result;
        // 子节点 Frame
        List<Frame> subframes;

        public void addSubframe(Frame subFrame) {
            if (subframes == null) {
                subframes = new ArrayList<>();
            }
            subframes.add(subFrame);
        }
    }


    static int func_loop(MultiTreeNode _head) {
        /*
        1. 入参看情况封装到 Frame 中, 用于压栈,出栈, 记录运行时信息. 一个节点处都会对应一个 Frame
        2. 递归的 base case 原样放到循环内部, 执行完 continue .
        3. 遇到递归调用处, 观察当前 Frame 压过栈的分支偏移量(任务提交过了,处理过了)
            3.1 达到分支个数, 说明, 所有子分支均已处理过, continue 下一轮迭代, 跳到 parent 处, 处理它的下一个子, 即我的后一个分支.
            3.2 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理.
        4. "自身" 处理, 原样放到循环内部对应位置.
         */

        if (_head == null) {
            return Integer.MIN_VALUE;
        }

        // 当前节点子节点处理到的位置 == 压过栈的子节点Frame
        Map<Frame, Integer> frameOffsetMap = new HashMap<>();

        Stack<Frame> stack = new Stack<Frame>();
        Frame rootFrame = new Frame(_head, null, null);
        stack.push(rootFrame);

        while (stack.isEmpty() == false) {
            Frame currFrame = stack.pop();
            List<MultiTreeNode> nexts = currFrame.node.getNexts();
            nexts = nexts == null ? new ArrayList<>() : nexts;
            // 递归退出条件
            if (nexts.size() == 0) {
                // 返回值记录在哪里?
                currFrame.result = currFrame.node.getValue();
                continue;
            }


            int currSubFork = frameOffsetMap.getOrDefault(currFrame, 0);

            // 所有子分支处理完了
            if (currSubFork == nexts.size()) {
                // 这里放后置处理逻辑
                // 递归中, 将所有子分支的最大值pk取最大和我自身再pk
                // 所有, 需要用到所有子分支的结果. 怎么知道所有子分支的结果?
                // 思路1: 实时更新. 子节点得到结果后, 立马和父节点当前值pk, 更新它.
                //   当前节点是子节点们已经pk后的结果, 所以这里直接取当前节点的值和父节点pk.
                // 思路2: 子节点每次有结果后, 只需要放到自己的 Frame 里存着就可以了, 这里, 取所有子 Frame 的结果pk, 作为我的结果
                //   ? 怎么获取所有子节点 Frame ?
                // 思路3: 子节点结果上报给父节点, 父节点 Frame 有个容器用于暂存所有子节点的结果, 之后需要用的到时候拿来用, 这里是取最大值, 就是拿来pk

                int max = Integer.MIN_VALUE;
                for (Frame subframe : currFrame.subframes) {
                    max = Math.max(max, subframe.result);
                }
                // 所有子节点节点和自己的再次pk
                currFrame.result = Math.max(currFrame.node.getValue(), max);
                continue;
            }

            // 子分支未处理结束, 当前栈帧重新压回; 封装当前子栈帧压入; 更新压过的子分支偏移量

            // 1. 取出当前要处理的分支的节点 currHandlePoint
            MultiTreeNode currHandleChild = nexts.get(currSubFork);

            // 2 然后, 压栈
            stack.push(currFrame);
            Frame subFrame = new Frame(currHandleChild, null, null);
            stack.push(subFrame);
            currFrame.addSubframe(subFrame);
            frameOffsetMap.put(currFrame, currSubFork + 1);
        }

        // 最后结果在 rootFrame 里面
        return rootFrame.result;
    }


}
